//1146.快照数组
//https://leetcode.cn/problems/snapshot-array
class SnapshotArray {
    int newid;
    vector<vector<pair<int,int>>> nums;
public:
    SnapshotArray(int length) :newid(0), nums(length) {}

    void set(int index, int val) {
        nums[index].push_back({newid,val});
    }

    int snap() {
        return newid++;
    }

    int get(int index, int snap_id) {
        vector<pair<int,int>>& v = nums[index];
         int l = 0,r = v.size();
         while(l < r)
         {
            int mid = (l+r)/2;
            if(v[mid].first > snap_id) r = mid;
            else l = mid+1;
         }
         if(l == 0) return 0;
         return v[l-1].second;
    }
};